package LeetCode;

/**
 * @Classname LC337
 * @Description // https://leetcode-cn.com/problems/house-robber-iii/comments/ 打家劫舍3
 * @Date 2021/4/20 19:26
 * @Created by yin
 */
public class LC337 {
    public int rob(TreeNode root) {
        int[] ans = subRob(root);
        return Math.max(ans[0],ans[1]);
    }

    // dps
    public int[] subRob(TreeNode node) {
        // 返回一个数组，分别存放抢劫这个节点的最高收入和不抢劫这个节点的最高收入
        if (node == null) return new int[]{0, 0};
        if (node.left == null && node.right == null) return new int[]{node.val, 0};
        int[] ans = new int[2];
        // 如果不抢，那子左右子节点都可以抢，怎么抢都可以
        int[] lefts = subRob(node.left);
        int[] rights = subRob(node.right);
        ans[1] = Math.max(lefts[0],lefts[1])+Math.max(rights[0],rights[1]);
        // 如果抢，那只能抢子节点中不抢的路径
        ans[0] = lefts[1]+rights[1]+node.val;
        return ans;
    }
}
